 %!TEX program = xelatex
\documentclass[lang=cn,10pt]{elegantbook}

% 本文档命令
\usepackage{array,url}
\newcommand{\ccr}[1]{\makecell{{\color{#1}\rule{1cm}{1cm}}}}
\newcommand{\code}[1]{\lstinline{#1}}


% 文档区
\begin{document}

\chapter*{数值分析作业--Week4}

\begin{problem}
将十进制整数477化为$\beta=2$的正规浮点数。
\end{problem}
\begin{proof}
有如下余数表
\begin{center}
\begin{tabular}{c|c}
    477 & 1 \\
    238 & 0 \\
    119 & 1 \\
     59 & 1 \\
     29 & 1 \\
     14 & 0 \\
      7 & 1 \\
      3 & 1 \\
      1 & 1 \\
\end{tabular}
\end{center}
由熟知算法，得
\[477 = (1.11011101)_2\times 2^8\]
\end{proof}
\vspace{1.5em}

\begin{problem}
将十进制分数$\dfrac{3}{5}$化为$\beta=2$的正规浮点数。
\end{problem}
\begin{proof}
有如下余数表
\begin{center}
\begin{tabular}{c|c}
    $\tfrac{3}{5}$ & 0 \\
    $\tfrac{6}{5}$ & 1 \\
    $\tfrac{2}{5}$ & 0 \\
    $\tfrac{4}{5}$ & 0 \\
    $\tfrac{8}{5}$ & 1 \\
    $\tfrac{6}{5}$ & 1 \\
\end{tabular}
\end{center}
由熟知算法，得
\[\dfrac{3}{5} = (1.\dot{0}01\dot{1})_2\times 2^{-1}\]
\end{proof}
\vspace{1.5em}

\begin{problem}
设$x=\beta^e,e\in\mathbb{Z},L<e<U$且$x$是$\mathbb{F}$中的一个正规浮点数，其中$x_L,x_R\in\mathbb{F}$是两个与$x$相邻的正规浮点数且$x_L<x<x_R$，证明$x_R-x=\beta(x-x_L)$。
\end{problem}
\begin{proof}
来证明
\[x_L = (\beta-\beta^{1-p})\beta^{e-1},\qquad x_R=(1+\beta^{1-p})\beta^e\]
任取$y\in\mathbb{F}$，不妨$y=m_y\times \beta^q$是正规的且与$x$相邻，若$q>e$，显然$y>(1+\beta^{1-p})\beta^e>x$；若$q<e-1$,显然$y<(\beta-\beta^{1-p})\beta^{e-1}<x$，矛盾，因此$q=e$或$q=e-1$。\par
若$q=e$，则必然有$m_y\geq 1+\beta^{1-p}$，根据相邻性$m_y \leq 1+\beta^{1-p}$，则$y=(1+\beta^{1-p})\beta^e$，由于$y>x$，故$x_R=(1+\beta^{1-p})\beta^e>x$。\par
若$q=e-1$，则必然有$m_y\leq \beta-\beta^{1-p}$，根据相邻性$m_y \geq \beta-\beta^{1-p}$，则$y=(\beta-\beta^{1-p})\beta^{e-1}$，由于$y>x$，故$x_L=(\beta-\beta^{1-p})\beta^{e-1}$。\par
综上，我们有
\[ x_R-x = \beta^{1+e-p} = \beta\cdot\beta^{e-p} = \beta(x-x_L)\]
即证。
\end{proof}
\vspace{1.5em}

\begin{problem}
通过问题2中的结论，找到两个在IEEE 754单精度单精度标准下与$x=\tfrac{3}{5}$相邻的正规浮点数，试求$\text{fl}(x)$与相对舍入误差。
\end{problem}
\begin{proof}
IEEE 754单精度标准有
\[\beta = 2,\qquad p = 23(\text{去除符号位})\]
因此显然
\[\dfrac{3}{5} = (1.\dot{0}0110011001100110011001\dot{1})_2 \times 2^{-1} \]
可以得到两个与$\dfrac{3}{5}$相邻的正规浮点数
\[\begin{cases}
(\dfrac{3}{5})_L = (1.0011001100110011001100)_2 \times 2^{-1} \\ \\
(\dfrac{3}{5})_R = (1.00110011001100110011101)_2 \times 2^{-1} 
\end{cases}
\]
从而
\[ \text{fl}(\dfrac{3}{5})=(1.0011001100110011001101)_2 \times 2^{-1}= (1-\dfrac{3}{5})\times 2^{-24}\]
且得到相对舍入误差
\[E_{\text{rel}}(\text{fl}(\dfrac{3}{5})) = \dfrac{2}{3}\times 2^{-24}\]

\end{proof}
\vspace{1.5em}

\begin{problem}
若IEEE 754单精度标准不将实数舍入到最近的一个$x\in\mathcal{F}$，只是简单的丢弃多余位，则单位舍入将会是多少。
\end{problem}
\begin{proof}
对于一个浮点数系统，显然简单丢弃位数得到的舍入误差的上确界为
\[\beta^{1-p}\]
对于IEEE 754标准，这个数为
\[2^{-22}\]
\end{proof}
\vspace{1.5em}

\begin{problem}
当$x=\tfrac{1}{4}$时，$1-\cos{x}$会损失几位精确度？
\end{problem}
\begin{proof}
首先由Taylor展开有
\[1-\cos{x} = \dfrac{x^2}{2!}-\dfrac{x^4}{4!}+\cdots\in (\dfrac{x^2}{2!}-\dfrac{x^4}{16},\dfrac{x^2}{2!})-\dfrac{x^4}{4!}+\dfrac{x^6}{6!}\]
再注意到
\[|\text{fl}(\cos{\dfrac{1}{4}}) - \dfrac{1}{4}| < \varepsilon_u\]
而$\varepsilon_u$一般认为小于$2^{-22}$，故
\[1-\text{fl}(\cos{\dfrac{1}{4}})\in (2^{-5}-2^{-12},2^{-5})\]
也即
\[1-\cos{\dfrac{1}{4}}\in(2^{-6},2^{-5})\]
这代表有$6$位精确度的损失。
\end{proof}
\vspace{1.5em}

\begin{problem}
给出至少两种方法避免c.c.当计算$1-\cos{x}$时。
\end{problem}
\begin{proof}
在题目5中已经说明，可以通过Taylor展开
\[1-\cos{x} = \dfrac{x^2}{2!}-\dfrac{x^4}{4!}+\cdots\]
计算，此外还显然可以通过计算
\[2\sin^2{\tfrac{x}{2}}=1-\cos{x}\]
来避免当$\cos{x}$太接近于1时产生的问题。
\end{proof}
\vspace{1.5em}

\begin{problem}
计算以下函数的条件数并指出它们在哪里较大。
\begin{itemize}
    \item $(x-1)^{\alpha}$
    \item $\ln x$
    \item $e^x$
    \item $\arccos x$
\end{itemize}
\end{problem}
\begin{proof}
条件数：
\[C_f(x)=|\dfrac{xf'(x)}{f(x)}|\]
只需找到$C_f(x)$的奇点：\par
$f(x)=(x-1)^{\alpha}$则
\[C_f(x)=|\dfrac{\alpha x}{x-1}|\]
有$x=1$是奇点，故条件数在$1$的邻域较大。\par
$f(x)=\ln x$则
\[C_f(x)=|\dfrac{1}{\ln x}|\]
有$x=1$是奇点，故条件数在$1$的邻域较大。\par
$f(x)=e^x$则
\[C_f(x)=|x|\]
有$x=\infty$是奇点，故条件数在$\infty$的邻域较大。\par
$f(x)=\arccos x$则
\[C_f(x)=|\dfrac{x}{\arccos x \sqrt{1-x^2}}|\]
有$x=\pm 1$为奇点，故条件数在$x,\ x\in\{-1,1\}$的邻域较大。\par
\end{proof}
\vspace{1.5em}

\begin{problem}
考虑函数$f(x)=1-e^{-x},x\in[0,1]$，证明：
\begin{itemize}
    \item 证明$\text{cond}_f(x)\leq 1,\forall x\in[0,1]$
    \item 设$A$是计算$f(x),x\in\mathbb{F}$的算法，假设指数函数允许小于机器舍入的相对误差进行计算，对$x\in[0,1]$估计$\text{cond}_A(x)$。
    \item 画出$\text{cond}_f(x)$与对$\text{cond}_A(x)$上界估计的曲线，并加以讨论。
\end{itemize}
\end{problem}
\begin{proof}
显然，对给定的$f$，有
\[C_f(x)=|\dfrac{xe^{-x}}{1-e^{-x}}|=\dfrac{x}{e^x-1}\leq 1,\forall x\in [0,1]\]
另外我们知道$f_A(x) = (1-(1+\delta_1)e^{-x})(1+\delta_2)=(1-e^{-x})(1+\delta(x))$，从而
\[\delta(x) = \delta_2-\delta_1\dfrac{1+\delta_2e^{-x}}{1-e^{-x}}\]
从而\[|\delta(x)|\leq |\delta_2|+|\delta_1||\dfrac{1+e^{-x}}{1-e^{-x}}| \leq\varepsilon_u \dfrac{2e^{-x}}{x}\]
上式由于$|\delta_1|,|\delta_2|<\varepsilon_u$，于是根据熟知定理4.76，我们可知
\[\text{cond}_A(x)\leq 2\dfrac{e^{-x}}{x}\]
并且可以把右式作为上面的估计。\par
我们有如下图像：
\begin{figure}[htbp]
    \centering
    \includegraphics[width = 0.6\textwidth]{cond.png}
\end{figure}\\
可见无奇异性的区域，$\text{cond}_A$与$\text{cond}_f$几乎一致，对于$x=0$附近，根据减法的消去现象，两者相差较大时是可预见到的。
\end{proof}
\vspace{1.5em}

\begin{problem}
求多项式
\[q(x) = \sum\limits_{i=0}^n a_ix^i,\qquad a_n =1, a_0\neq 0, a_i\in\mathbb{R}\]
的根可以考虑为对一个向量函数$f:\mathbb{R}^n\to\mathbb{C}$：
\[r = f(a_0,a_1,\cdots,a_{n-1})\]
写出基于1范数的逐元素条件数，并且对于Wilkinson问题，计算你的条件数，并且将结果与材料做对比，并加以讨论。
\end{problem}
\begin{proof}
对于
\[q(r) =  \sum\limits_{i=0}^n a_ir^i = 0\]
有
\[\dfrac{\partial q(r)}{\partial a_k} = r^k + q'(r)\dfrac{\partial r}{\partial a_k} = 0 \implies \dfrac{\partial r}{\partial a_k} = -\dfrac{r^k}{q'(r)}\]
从而设
\[\text{cond}_f(x) = ||A(x)|| \]
有
\[A_k(x) = |\dfrac{a_kr^{k-1}}{q'(r)}|\]
则可知
\[\text{cond}_f(x)=\sum\limits_{0\leq k \leq n}|\dfrac{a_kr^{k-1}}{q'(r)}|=\dfrac{\sum\limits_{k=0}^n|a_k||r|^{k}}{|rq'(r)|}\]
在Wilkinson 问题中，对根$k,1\leq k \leq p$, 容易知道对于根$k$有条件数
\[\dfrac{(k+p)!}{k!k!(p-k)!}\]
则对根$p$的条件数为
\[C_{2p}^p\]
对于较大的$p$，条件数较大，材料中相当于对$a_p$进行小扰动，可以推测相对误差大，与材料结论一致。
\end{proof}
\vspace{1.5em}

\begin{problem}
给出一个当中间寄存器精度为$2p$时，定理4.40不成立的例子。
\end{problem}
\begin{proof}
考虑以$\beta$为基的浮点数系统中的两个数$a,b$：
\[a = \beta^{1-p},\qquad b=\beta-\beta^{1-p}\]
在精度2p的寄存器中，$m_a/m_b$是如下结果：
\[(0.000\cdots0100\cdots000)_{\beta}\]
其中1在第$p+1$位，该数正规化并舍入后为$\beta^{1-p}$，相对误差为
\[|\dfrac{\beta^{1-p}-a/b}{a/b}| = \beta^{1-p} = 2\varepsilon_u\]
即是反例。
\end{proof}
\vspace{1.5em}

\begin{problem}
给出一个当中间寄存器精度为$2p$时，定理4.40不成立的例子。
\end{problem}
\begin{proof}
考虑以$\beta$为基的浮点数系统中的两个数$a,b$：
\[a = \beta^{1-p},\qquad b=\beta-\beta^{1-p}\]
在精度2p的寄存器中，$m_a/m_b$是如下结果：
\[(0.000\cdots0100\cdots000)_{\beta}\]
其中1在第$p+1$位，该数正规化并舍入后为$\beta^{1-p}$，相对误差为
\[|\dfrac{\beta^{1-p}-a/b}{a/b}| = \beta^{1-p} = 2\varepsilon_u\]
即是反例。
\end{proof}
\vspace{1.5em}

\begin{problem}
若二分法使用IEEE 754 单精度标准的浮点数，在$[128,129]$区间求根，那么能否保证绝对误差小于$10^{-6}$？
\end{problem}
\begin{proof}
考虑这个区间中根的储存形式\
\[(1.00000a_1a_2\cdots a_{15}a_{16})_2 \times 2^7,\quad a_i\in\{0,1\},1\leq i\leq 16\]
因此，这部分根的精度为$2^{-16}>10^{-6}$，故不能保证。
\end{proof}
\vspace{1.5em}

\begin{problem}
用矩阵条件数解释为何用立方样条拟合曲线时，两个相邻样本点距离远小于其他相邻样本点会导致结果不准确。
\end{problem}
\begin{proof}
注意到对于立方样条，我们令$m_i=s'(f;x_i)$总有如下关系：
\[\lambda_im_{i-1}+2m_i+\mu_im_{i+1}=3\mu_if_{[x_i,x_{i+1}]}+3\lambda_if_{[x_{i-1},x_i]}\]
根据假设$x_{k+1}-x_k \approx 0, \mu_{k+1}\approx 0, \lambda_k\approx 0$
，于是可看作$$m_{k+1} + 2m_k = 3f[x_k,x_{k+1}] = 3\dfrac{f(x_k)-f(x_{k+1})}{x_k-x_{k+1}}$$
上式的两个减法运算在$x_k-x_{k+1}\approx 0$时会产生极大的精度损失，因此对于此处的拟合会有较大误差。
\end{proof}
\vspace{1.5em}

\end{document}
